package zhengqc.list;

public class DoublyLinkedListD<E> extends AbstractList<E> {
    private class Node {
        public Node prev;
        public E element;
        public Node next;
        public Node(Node prev, E element, Node next) {
            this.prev = prev;
            this.element = element;
            this.next = next;
        }
        public Node(E element) {
            this(null, element, null);
        }
        public Node() {
            this(null, null, null);
        }
        @Override
        public String toString() {
            return element.toString();
        }
    }
    /* 双向链表虚拟头指针 */
    private Node dummyHead;
    /* 双向链表虚拟尾指针 */
    private Node dummyTail;

    public DoublyLinkedListD() {
        this.dummyHead = new Node(null, null, null);
        this.dummyTail = new Node(this.dummyHead, null, null);
        this.dummyHead.next = this.dummyTail;
        this.size = 0;
    }

    /* 获取双向链表 index 位置对应节点对象的引用 */
    private Node getNode(int index) {
        if (index < -1 || index > size) {
            throw new IndexOutOfBoundsException(String.format("Index: %d, Size: %d", index, this.size));
        }
        Node node = null;
        if (index < (this.size >> 1)) {
            node = this.dummyHead;
            for (int i = -1; i < index; ++i) {
                node = node.next;
            }
        } else {
            node = this.dummyTail;
            for (int i = this.size; i > index; --i) {
                node = node.prev;
            }
        }
        return node;
    }

    @Override /* 获取双向链表指定元素的位置 */
    public int indexOf(E element) {
        Node current = dummyHead.next;
        for (int i = 0; current != this.dummyTail; ++i) {
            if (current.element.equals(element)) {
                return i;
            }
            current = current.next;
        }
        return ELEMENT_NOT_FOUND;
    }

    @Override /* 清空双向链表的所有元素 */
    public void clear() {
        Node current = this.dummyHead.next;
        while (current != this.dummyTail) {
            Node next = current.next;
            current.prev = null;
            current.next = null;
            current = next;
        }
        this.dummyHead.next = this.dummyTail;
        this.dummyTail.prev = this.dummyHead;
        this.size = 0;
    }

    @Override /* 在双向链表的 index 位置添加元素 element*/
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        Node current = getNode(index);
        Node newNode = new Node(current.prev, element, current);
        current.prev.next = newNode;
        current.prev = newNode;
        ++ this.size;
    }

    @Override /* 在双向链表开始位置添加元素 element*/
    public void addFirst(E element) {
        add(0, element);
    }

    @Override /* 在双向链表末尾位置添加元素 element*/
    public void addLast(E element) {
        add(this.size, element);
    }

    @Override /* 删除双向链表的 index 位置的元素 */
    public E remove(int index) {
        rangeCheck(index);
        Node current = getNode(index);
        current.prev.next = current.next;
        current.next.prev = current.prev;
        -- this.size;
        return current.element;
    }

    @Override /* 删除双向链表开始位置的元素 */
    public E removeFirst() {
        return remove(0);
    }

    @Override /* 删除双向链表末尾位置的元素 */
    public E removeLast() {
        return remove(this.size-1);
    }

    @Override /* 设置双向链表 index 位置的元素 */
    public void set(int index, E element) {
        getNode(index).element = element;
    }

    @Override /* 获取双向链表 index 位置的元素 */
    public E get(int index) {
        return getNode(index).element;
    }
    @Override /* 双向链表转数组 */
    public E[] toArray() {
        E[] array = (E[]) (new Object[this.size]);
        Node current = dummyHead.next;
        for (int i = 0; current != this.dummyTail; ++i) {
            array[i] = current.element;
            current = current.next;
        }
        return array;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("DoublyLinkedListD: size=").append(this.size).append(", content=[");
        Node current = dummyHead.next;
        while (current != this.dummyTail) {
            sb.append(current.element.toString()).append("->");
            current = current.next;
        }
        sb.append("NULL]");
        return sb.toString();
    }
}
